//
// Created by Administrator on 2021/7/28.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> countSmaller_by_borce(vector<int> &nums) {
        // 暴力
        int n = (int) nums.size();
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int counter = 0;
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] < nums[i]) ++counter;
            }
            ans.push_back(counter);
        }
        return ans;
    }

    vector<int> countSmaller(vector<int> &nums) {
        vector<int> sortedNums;
        vector<int> ans;
        for (int i = (int) nums.size() - 1; i >= 0; --i) {
            auto index = lower_bound(sortedNums.begin(), sortedNums.end(), nums[i]);
            ans.push_back(index - sortedNums.begin());
            sortedNums.insert(index, nums[i]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
        // 超时 62/65
    }
};

int main() {
    vector<int> nums{5, 2, 6, 1};
    Solution solution;
    auto ans = solution.countSmaller_by_borce(nums);
    for (auto &x:ans) cout << x << endl;

    ans = solution.countSmaller(nums);
    for (auto &x:ans) cout << x << endl;
    return 0;
}